People are increasingly interacting with computers and other electronic devices in new and interesting ways. For example, object tracking can be implemented for recognizing certain user gestures, such as head nods or shakes, eye winks or other ocular motion, or hand and/or finger gestures, as input for the device. Object tracking can also be utilized for advanced device security features such as ensuring “live” facial recognition, fingerprinting, retinal scanning, or identification based on gait. Devices capable of object tracking can also be configured for video editing techniques such as video stabilization (e.g., to remove jitter) or to render smooth camera motions due to panning, tilting, or dollying in/dollying out. There are, however, many challenges to properly tracking an object due to, for example, abrupt motions, changes in appearance or background, device motion, among others. Further, factors such as image sensor and lens characteristics, illumination conditions, noise, and occlusion can also affect how an object is represented from image to image or frame to frame. Additionally, the processing requirements for adequate object tracking can often be at odds with the objective of minimizing processing and power use on portable computing devices.